package com.zack.algorithm.trie;

/**
* email: miao.du@shuruitech.com
* author: zack
**/
import java.io.File;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.concurrent.CopyOnWriteArrayList;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class Trie implements Serializable {
    private static final long serialVersionUID = -2933923081228664509L;
    private static Logger logger = LoggerFactory.getLogger(Trie.class);
    public TrieNode rootNode;

    // 表示这个Trie树有多少个Trie Node
    public int nodeNum = 0;

    public int getNodeNum() {
        return nodeNum;
    }

    public void setNodeNum(int nodeNum) {
        this.nodeNum = nodeNum;
    }

    public Trie() {
        rootNode = new TrieNode('#');
    }

    /**
     *
     * 
     * @param word
     *            ： 大号
     * @param type
     *            : GOODS 就是说添加一个节点， 这个word的类型是 "产品类型"
     * 
     *            我可以添加相同的word多次， 每次可以不同类型， ， 最后这个word的节点里会有一个list存储所有这些类型。
     */
    public void insert(String word, String type) {
        word = word.toLowerCase();
        if (word.isEmpty() || type.isEmpty()) {
            return;
        }
        TrieNode exitNode = searchWordRtNode(word);
        if (null != exitNode) {
            if (exitNode.getTypeList().contains(type)) {
                return;
            } else {
                exitNode.getTypeList().add(type);
                return;
            }
        }
        // 释放资源
        exitNode = null;
        TrieNode current = rootNode;
        for (int i = 0; i < word.length(); i++) {
            TrieNode child = current.subNodes(word.charAt(i));
            if (child != null) {
                current = child;
            } else {
                TrieNode nodeTrie = new TrieNode(word.charAt(i));
                nodeTrie.fatherNode = current;
                current.childNodes.add(nodeTrie);
                nodeNum++;
                current = current.subNodes(word.charAt(i));
            }
            current.preFixFreq++;
        }
        current.isEnd = true;
        current.setWholeWord(word);
        List<String> newcuiList = new ArrayList<>();
        newcuiList.add(type);
        current.setTypeList(newcuiList);
        // 释放资源
        current = null;
        newcuiList = null;
    }

    /**
     * 可不用这个方法。
     * 
     * @param word
     *            ：
     * @param metaMap
     */
    public void insert(String word, Map<String, String> metaMap) {
        word = word.toLowerCase();
        Set<String> kSet1 = metaMap.keySet();
        String cuiStr = "";
        for (String key1 : kSet1) {
            if (key1.equals("type")) {
                cuiStr = metaMap.get(key1);
            }
        }
        TrieNode exitNode = searchWordRtNode(word);
        if (null != exitNode) {
            if (exitNode.getTypeList().contains(cuiStr)) {
                return;
            } else {
                exitNode.getTypeList().add(cuiStr);
                return;
            }
        }

        TrieNode current = rootNode;
        for (int i = 0; i < word.length(); i++) {
            TrieNode child = current.subNodes(word.charAt(i));
            if (child != null) {
                current = child;
            } else {
                TrieNode nodeTrie = new TrieNode(word.charAt(i));
                nodeTrie.fatherNode = current;
                current.childNodes.add(nodeTrie);
                nodeNum++;
                current = current.subNodes(word.charAt(i));
            }
            current.preFixFreq++;
        }
        current.isEnd = true;
        current.setWholeWord(word);
        List<String> newcuiList = new ArrayList<>();
        newcuiList.add(cuiStr);
        current.setTypeList(newcuiList);
    }

    /**
     * 
     * @param word
     * @return
     */
    // public boolean search(String word) {
    // word = word.toLowerCase();
    // TrieNode currNodes = rootNode;
    //
    // for (int i = 0; i < word.length(); i++) {
    // TrieNode tempNodes = currNodes.subNodes(word.charAt(i));
    // if (tempNodes != null) {
    // currNodes = tempNodes;
    // } else {
    // return false;
    // }
    // }
    // if (currNodes.isEnd) {
    // return true;
    // }
    // return false;
    // }

    public boolean search(String word) {
        word = word.toLowerCase();
        TrieNode currNode = rootNode;
        for (int i = 0; i < word.length(); i++) {
            TrieNodeAndWordPosition trieNodeAndWordPosition = containsWordFromsubnode(currNode.getChildNodes(), i,
                    word);

            // -----------------------------------Delete Below Block----------------just for
            // test------------------------------------------------------------------------
            // if (null != trieNodeAndWordPosition) {
            // if (trieNodeAndWordPosition.getTrieNode().nodeChar == 0) {
            // System.out.println("=====: "+i+"---TrieNodeAndWordPosition:
            // "+trieNodeAndWordPosition.position+"------"+trieNodeAndWordPosition.getTrieNode().getCompactStr());
            // }else {
            // System.out.println("=====: "+i+"---TrieNodeAndWordPosition:
            // "+trieNodeAndWordPosition.position+"------"+trieNodeAndWordPosition.getTrieNode().getNodeChar());
            // }
            // }else{
            // System.out.println("=====: "+i+"---null");
            // }
            // -----------------------------------------------------Delete Above
            // Block-----------------just
            // test---------------------------------------------------------

            if (trieNodeAndWordPosition != null) {
                currNode = trieNodeAndWordPosition.getTrieNode();
                i = trieNodeAndWordPosition.getPosition();
            } else {
                return false;
            }
        }
        if (currNode.isEnd) {
            return true;
        }
        return false;
    }

    private TrieNodeAndWordPosition containsWordFromsubnode(List<TrieNode> subNodes, int charFrom, String word) {
        word = word.toLowerCase();
        if (null == subNodes) {
            return null;
        }
        for (TrieNode subNode : subNodes) {
            if (subNode.nodeChar != 0) {
                if (word.charAt(charFrom) == subNode.nodeChar) {
                    TrieNodeAndWordPosition trieNodeAndWordPosition = new TrieNodeAndWordPosition(charFrom, subNode);
                    return trieNodeAndWordPosition;
                }
            } else {
                int length = subNode.compactStr.length();
                int toPosition = charFrom + length;
                if (toPosition > word.length()) {
                    continue;
                }
                word.toLowerCase().substring(charFrom, toPosition);
                if (subNode.compactStr.equals(word.substring(charFrom, charFrom + length))) {
                    TrieNodeAndWordPosition trieNodeAndWordPosition = new TrieNodeAndWordPosition(toPosition - 1,
                            subNode);
                    return trieNodeAndWordPosition;
                }
            }
        }
        return null;
    }

    /**
     * 
     * @param word
     * @return
     */
    public TrieNode searchWordRtNode(String word) {
        word = word.toLowerCase();
        TrieNode currNodes = rootNode;
        for (int i = 0; i < word.length(); i++) {
            // TrieNode tempNode = currNodes.subNodes(word.charAt(i));
            TrieNodeAndWordPosition trieNodeAndWordPosition = containsWordFromsubnode(currNodes.getChildNodes(), i,
                    word);
            if (trieNodeAndWordPosition != null) {
                currNodes = trieNodeAndWordPosition.getTrieNode();
                i = trieNodeAndWordPosition.getPosition();
            } else {
                return null;
            }
        }
        if (currNodes.isEnd) {
            return currNodes;
        }
        return null;
    }

    /**
     * @param word
     * @return
     */
    public TrieNode searchPrefixRtNode(String word) {
        word = word.toLowerCase();
        TrieNode currNode = rootNode;
        for (int i = 0; i < word.length(); i++) {
            // TrieNode tempNodes = currNodes.subNodes(word.charAt(i));
            TrieNodeAndWordPosition trieNodeAndWordPosition = containsWordFromsubnode(currNode.getChildNodes(), i,
                    word);
            if (trieNodeAndWordPosition != null) {
                currNode = trieNodeAndWordPosition.trieNode;
                i = trieNodeAndWordPosition.getPosition();
                // System.out.println("tempNodes 不等于null， 此时word 是个： ("+word.charAt(i)+")."+"
                // tempNodes 输出CuiList.size: "+tempNodes.getCuiList().size());
            } else {
                return null;
            }
        }
        return currNode;
    }

    /**
     * @param word
     */
    public void deleteWord(String word) {
        word = word.toLowerCase();
        if (search(word) == false)
            return;
        TrieNode current = rootNode;
        for (char c : word.toCharArray()) {
            TrieNode child = current.subNodes(c);
            if (child.preFixFreq == 1) {
                current.childNodes.remove(child);
                nodeNum--;
                return;
            } else {
                child.preFixFreq--;
                current = child;
            }
        }
        current.isEnd = false;
        current.setTypeList(null);
        current.setWholeWord(null);
    }

    /*
     * @see java.lang.Object#toString()
     */
    public String toString() {
        String allWordsString = "";
        getAllWordFromTrie();
        List<List<TrieNode>> printNodeList = getAllWordFromTrie();
        for (List<TrieNode> nodeList : printNodeList) {
            for (TrieNode node : nodeList) {
                allWordsString = allWordsString + node.nodeChar;
            }
            allWordsString = allWordsString + "\n";
        }
        return allWordsString;
    }

    /*
     * @see java.lang.Object#toString()
     */
    public List<List<TrieNode>> getAllWordFromTrie() {
        LinkedList<TrieNode> printNodeList = new LinkedList<>();
        printNodeList.add(rootNode);
        List<List<TrieNode>> wordsList = new LinkedList<>();
        dfsTrie(printNodeList, rootNode, 1, wordsList);
        return wordsList;
    }

    /**
     * @param printNodeList
     * @param currNode
     * @param wordCount
     * @param wordsList
     */
    public void dfsTrie(LinkedList<TrieNode> printNodeList, TrieNode currNode, int wordCount,
            List<List<TrieNode>> wordsList) {
        if (currNode.isEnd) {
            List<TrieNode> tempList = new LinkedList<>();
            for (TrieNode tN : printNodeList) {
                tempList.add(tN);
            }
            wordsList.add(tempList);
        }
        if (null == currNode.childNodes || currNode.childNodes.size() == 0) {
            return;
        }
        for (int k = 0; k < currNode.childNodes.size(); k++) {
            TrieNode tempCurrNode = currNode.childNodes.get(k);
            printNodeList.add(tempCurrNode);
            dfsTrie(printNodeList, tempCurrNode, wordCount + 1, wordsList);
            printNodeList.remove(tempCurrNode);
        }
    }

    // public static void getAllNodes(Trie aTrie){
    // List<TrieNode> trieNodes = new ArrayList<>();
    // }

    /**
     * @param nodes
     * @return
     */
    public static String printWordFromList(LinkedList<TrieNode> nodes) {
        String wordsString = "";
        for (TrieNode tnode : nodes) {
            wordsString = wordsString + tnode.nodeChar;
            System.out.print(tnode.nodeChar);
        }
        for (String aCui : nodes.get(nodes.size() - 1).getTypeList()) {
            System.out.print("\t" + aCui);
        }
        return wordsString;
    }

    /**
     * @param filePath
     * @param trieObj
     */
    public static void serialize(String filePath, Trie trieObj) {
        if (null == filePath || filePath.equals("") || filePath.equals(" ")) {
            filePath = "doc/abc.txt";
        }
        try {
            File file = new File(filePath);
            if (!file.exists()) {
                file.createNewFile();
            }
            ObjectOutputStream objStream = new ObjectOutputStream(new FileOutputStream(file));
            objStream.writeObject(trieObj);
            objStream.flush();
            objStream.close();
        } catch (Exception e) {
            logger.error("Error Occurs when to Serialize dictionary", e);
        }
        logger.info("Finish Serialing Trie！");
    }

    /**
     * @param serializeFile
     * @return
     */
    public static Trie deSerialize(String serializeFile) {
        if (null == serializeFile || serializeFile.equals("") || serializeFile.equals(" ")) {
            logger.error("Your file is not a serialized File.", new IllegalArgumentException());
        }
        ObjectInputStream oin = null;
        try {
            oin = new ObjectInputStream(Trie.class.getClassLoader().getResourceAsStream(serializeFile));
            Trie trieObj = (Trie) oin.readObject();
            oin.close();
            return trieObj;
        } catch (Exception e) {
            logger.error("De-serialize occurs error", e);
        }
        return null;
    }

    /**
     * @return 第一种压缩方式： 压缩Trie树， 把连续的节点压缩成一个（当连续的节点都没有其他节点相连的时候，也就是说可以被压缩的节点必须满足，
     *         freq=1） 例如 abcde， 与 abckx 如果trie只有这两个词， 那么 d与e可以被压缩到一个节点里面， k，x
     *         可以被压缩到一个节点里， 而a与b与c则不能做这个压缩， 因为，他们的出现频率都不是1
     * 
     *         第二种压缩方式： 只要这个节点的子节点个数为1， 把这样连续的子节点进行压缩，直到压缩到最后一个 子节点个数为1的节点的子节点。
     *         例如A的子节点个数为1也就是B， 那么无论B有几个子节点，都可以把A和B压缩到一个节点里面去。
     * 
     *         注意有些节点如果是结束节点则不应该进行压缩。 一旦压缩好的Trie树，是不允许动态添加节点和删除节点的。
     */
    public static Trie compactTrie(Trie aTrie) {
        logger.info("Before compressing: " + aTrie.nodeNum + "\nCompressing the Trie...");
        long a = System.currentTimeMillis();
        // just to use Queue
        PriorityQueue<TrieNode> nodesQueue = new PriorityQueue<>(new Comparator<TrieNode>() {
            @Override
            public int compare(TrieNode o1, TrieNode o2) {
                return 0;
            }
        });
        if (null == aTrie.rootNode || aTrie.rootNode.getChildNodes().size() < 1) {
            return aTrie;
        }
        nodesQueue.addAll(aTrie.rootNode.getChildNodes());

        StringBuilder compactStr = new StringBuilder();
        while (nodesQueue.size() > 0) {
            TrieNode currentNode = nodesQueue.poll();
            TrieNode fatherNode = currentNode.fatherNode;
            TrieNode tempCurrentNode = currentNode;
            TrieNode newNode = new TrieNode('\0');
            int cntNum = 0;
            compactStr.setLength(0);
            while (currentNode.childNodes.size() == 1 && !currentNode.isEnd) {
                cntNum++;
                compactStr.append(currentNode.nodeChar);

                // 记录当前节点，把所有连续的这种节点组合成一个节点。
                currentNode = currentNode.childNodes.get(0);
            }
            if (cntNum >= 1) {
                aTrie.nodeNum = aTrie.nodeNum - cntNum;
                // 1. 把currentNode的信息赋值给newNode里面
                compactStr.append(currentNode.nodeChar);
                newNode.isEnd = currentNode.isEnd;
                newNode.fatherNode = fatherNode;

                newNode.setCompactStr(compactStr.toString());
                newNode.preFixFreq = currentNode.preFixFreq;
                newNode.setTypeList(currentNode.typeList);
                newNode.setWholeWord(currentNode.wholeWord);
                // 2. 从father的子节点里把tempCurrentNode删除， 然后添加引用指向newNode
                CopyOnWriteArrayList<TrieNode> cowList = new CopyOnWriteArrayList<>(fatherNode.childNodes);
                for (TrieNode trieNode : cowList) {
                    if (trieNode == tempCurrentNode) {
                        cowList.remove(trieNode);
                    }
                }
                cowList.add(newNode);
                LinkedList<TrieNode> childNodes = new LinkedList<>(cowList);
                fatherNode.setChildNodes(childNodes);

                // 3. 把current子节点赋值给newNode
                newNode.setChildNodes(currentNode.childNodes);
                // 4. 还要把所有子节点的父节点全部改成newNode
                for (TrieNode trieNode : newNode.childNodes) {
                    trieNode.setFatherNode(newNode);
                }
            } else {
                // 清理掉内存
                newNode = null;
            }
            // 这里再把子节点给添加进入queue里面， 也可以写成newNode,而不应该用currentNode，前提是null!=newNode
            if (null != newNode && null != newNode.childNodes && newNode.childNodes.size() >= 0) {
                nodesQueue.addAll(newNode.childNodes);
            } else if (null != currentNode && null != currentNode.childNodes && currentNode.childNodes.size() >= 0) {
                nodesQueue.addAll(currentNode.childNodes);
            }
        }
        long b = System.currentTimeMillis();
        logger.info("Finishing compressing......" + aTrie.nodeNum + "     -----------Compressing Time Cost: " + (b - a)
                + " ms.");
        return aTrie;
    }

    public List<TrieNode> getBfsFromTrie(Trie aTrie) {
        PriorityQueue<TrieNode> trieNodesQueue = new PriorityQueue<>(new Comparator<TrieNode>() {
            @Override
            public int compare(TrieNode o1, TrieNode o2) {
                return 0;
            }
        });
        trieNodesQueue.add(aTrie.rootNode);
        List<TrieNode> trieNodes = new ArrayList<>();
        while (trieNodesQueue.size() > 0) {
            TrieNode trieNode = trieNodesQueue.poll();
            trieNodes.add(trieNode);
            trieNodesQueue.addAll(trieNode.getChildNodes());
        }
        return trieNodes;
    }

    private static void printAllNodesBFS(Trie aTrie) {
        List<TrieNode> trieNodeList = aTrie.getBfsFromTrie(aTrie);
        for (TrieNode trieNode : trieNodeList) {
            if (trieNode.getNodeChar() == 0) {
                System.out.println("\t\t" + trieNode.getCompactStr() + "[IsEnd: ]" + trieNode.isEnd + "---[WholeWord]: "
                        + trieNode.getWholeWord() + " [CuiList ]: " + trieNode.getTypeList().size());
            } else {
                System.out
                        .println("\t\t" + trieNode.getNodeChar() + "---[IsEnd]: " + trieNode.isEnd + "---[WholeWord]: "
                                + trieNode.getWholeWord() + " [CuiList ]: " + trieNode.getTypeList().size());
            }
        }
    }

    private static void tempPrintTrieNodes(List<TrieNode> trieNodes) {
        for (TrieNode trieNode : trieNodes) {
            if (trieNode.getNodeChar() == 0) {
                System.out.print(trieNode.getCompactStr() + "\t");
            } else {
                System.out.print(trieNode.getNodeChar() + "\t");
            }
        }
    }
}

class TrieNodeAndWordPosition {
    int position = 0;
    TrieNode trieNode;

    public TrieNodeAndWordPosition(int position, TrieNode trieNode) {
        super();
        this.position = position;
        this.trieNode = trieNode;
    }

    public int getPosition() {
        return position;
    }

    public void setPosition(int position) {
        this.position = position;
    }

    public TrieNode getTrieNode() {
        return trieNode;
    }

    public void setTrieNode(TrieNode trieNode) {
        this.trieNode = trieNode;
    }
}
